#include "graph.h"
#include "func_generales.h"



#include <iostream>
#include <fstream>

#include <string>
#include <string.h>//

using namespace std;

Path::Path() {
    path = new list<int>;
}

Path::Path(Path * p) {
    path = new list<int>;
    for (list<int>::iterator it = p->path->begin(); it != p->path->end(); it++) {
        path->push_back(*it);
    }
}

bool Path::IsEmpty() {
    return path->empty();
}

bool FindIJ(Path* p, int i, int j, list<int>::iterator & itA, list<int>::iterator & itB) {
    list<int>::iterator it1A = p->path->begin();
    list<int>::iterator it1B = p->path->end();

    while (it1A != it1B && *it1A != i && *it1A != j)
        it1A++;

    if (it1A == it1B)
        return false;
    else
        itA = it1A;

    int _e = (*itA == i ? j : i);

    while (it1A != it1B && *it1A != _e)
        it1A++;

    if (it1A == it1B)
        return false;
    else
        itB = it1A;

    return true;
}

void Path::Replace(Path * p, int u, int v) {
    list<int>::iterator it1A, it1B;
    list<int>::iterator it2A, it2B;

    //cout << "u, v: " << u+1 << " " << v+1 << endl;
    //PrintPath(this);
    //PrintPath(p);
    int findA = FindIJ(this, u, v, it1A, it1B);
    int findB = FindIJ(p, u, v, it2A, it2B);
    //cout << "findA, findB: " << findA << " " << findB << endl;

    if (!findA || !findB) {
        cout << "[ERROR][Path::Replace]: Not found i or j" << "\n";
    } else {
        //cout << "it1A, it1B: " << *it1A +1 << " " << *it1B +1 <<"\n";
        //cout << "it2A, it2B: " << *it2A +1 << " " << *it2B +1 <<"\n";

        if (*it2A == *it1A) {
            it1A = it1B = path->erase(it1A, it1B);
            while (it2A != it2B) {
                it1A = path->insert(it1A, *it2A);
                it1A++;
                it2A++;
            }
        } else {
            it1A = it1B = path->erase(it1A, it1B);
            while (it2A != it2B) {
                it1A = path->insert(it1A, *it2B);
                it1A++;
                it2B--;
            }
        }
    }

    //PrintPath(this); cout << endl;
    //cout << endl;

}

Path* Path::SubPath(int i, int j) {

    list<int>::iterator itA;
    list<int>::iterator itB;
    Path * sub_path = new Path();

    if (!FindIJ(this, i, j, itA, itB)) {
        cout << "[ERROR][Path::SubPath]: Not found i or j" << "\n";
        return NULL;
    }

    itB++;

    for (list<int>::iterator it = itA; it != itB; ++it)
        sub_path->path->push_front(*it);

    return sub_path;
}

bool Path::Contains(Path* p) {
    int i = p->path->front();
    int j = p->path->back();

    list<int>::iterator it1A, it1B;
    list<int>::iterator it2A, it2B;

    if (!FindIJ(this, i, j, it1A, it1B)) {
        //cout << "Not found i or j" << endl;
        return false;
    }

    if (!FindIJ(p, i, j, it2A, it2B)) {
        cout << "[ERROR][Path::Contains]: Not found i or j" << "\n";
        return false;
    }

    if (*it2A == *it1A) {
        while (it1A != it1B && it2A != it2B) {
            if (*it1A != *it2A) return false;

            it1A++;
            it2A++;
        }

        if (*it1A == *it2A) return true;
    } else {
        while (it1A != it1B && it2A != it2B) {
            if (*it1A != *it2B) return false;

            it1A++;
            it2B--;
        }

        if (*it1A == *it2B) return true;
    }

    return false;
}

bool Path::Contains(int node) {

    for (list<int>::iterator it = path->begin(); it != path->end(); ++it)
        if ((*it) == node) return true;

    return false;
}

bool Path::Contains(pair<int, int> * edge) {
    list<int>::iterator _it;
    for (list<int>::iterator it = path->begin(); it != path->end(); ++it) {
        if (*it == edge->first || *it == edge->second) {
            if (*it == edge->first) {
                _it = it;
                _it++;
                return (*_it == edge->second);
            } else {
                _it = it;
                _it++;
                return (*_it == edge->first);
            }
        }
    }
    return false;
}

int Path::Length() {
    return path->size();
}

int& Path::operator[](int x) {
    list<int>::iterator it = path->begin();
    advance(it, x);

    return (*it);
}

int Path::Size() {
    return path->size();
}

Path::~Path() {

    path->clear();
    delete path;
}

// Constructors

PathMatrix::PathMatrix() {
    sizeP = 0;
    P = NULL;
}

PathMatrix::PathMatrix(int size) {
    sizeP = size;

    P = new list<Path*> **[size];

    for (int i = 0; i < size; i++) {
        P[i] = new list<Path*> *[size];
        for (int j = i; j < size; j++) {
            P[i][j] = new list<Path*>;
        }
    }

}

PathMatrix::PathMatrix(PathMatrix * _PM) {
    sizeP = _PM->sizeP;

    P = new list<Path*> **[sizeP];

    for (int i = 0; i < sizeP; i++) {
        P[i] = new list<Path*> *[sizeP];
        for (int j = i; j < sizeP; j++) {
            P[i][j] = new list<Path*>();
            for (list<Path*>::iterator it = _PM->P[i][j]->begin(); it != _PM->P[i][j]->end(); ++it)
                P[i][j]->push_front(new Path(*it));
        }
    }

}

bool PathMatrix::IsNodeDisjointTo(Path* p, int i, int j) {
    Path * path_aux;
    int aux;

    if (i > j) {
        aux = i;
        i = j;
        j = aux;
    }

    for (list<Path * >::iterator it0 = P[i][j]->begin(); it0 != P[i][j]->end(); ++it0) {
        path_aux = *it0;

        if (path_aux->Length() == 2) {
            if ((path_aux->path->front() == i && path_aux->path->back() == j) || (path_aux->path->front() == j && path_aux->path->back() == i)) {
                // el camino es la ariasta (i, j) o (j, i)
                return false;
            }
        } else {
            for (list<int>::iterator it1 = p->path->begin(); it1 != p->path->end(); ++it1)
                if (*it1 != i && *it1 != j && path_aux->Contains(*it1)) return false;
        }
    }

    return true;
}

void PathMatrix::Add(Path* p, int i, int j) {
    if (i <= j)
        P[i][j]->push_front(p);
    else
        P[j][i]->push_front(p);
}

void PathMatrix::Update(Path* p_old, Path* p_new) {

    for (int i = 0; i < sizeP; i++) {
        for (int j = i; j < sizeP; j++) {
            for (list<Path*>::iterator it = P[i][j]->begin(); it != P[i][j]->end(); ++it)
                if ((*it)->Contains(p_old)) (*it)->Replace(p_new, p_old->path->front(), p_old->path->back());
        }
    }
}

bool PathMatrix::Contains(Path * p, int i, int j) {

    for (list<Path*>::iterator it = P[i][j]->begin(); it != P[i][j]->end(); ++it)
        if ((*it)->Contains(p)) return true;

    return false;
}

list<Path*> **& PathMatrix::operator[](int x) {
    return P[x];
}

PathMatrix::~PathMatrix() {
    if (P) {
        for (int i = 0; i < sizeP; i++) {
            for (int j = i; j < sizeP; j++) {
                for (list<Path*>::iterator it = P[i][j]->begin(); it != P[i][j]->end(); ++it)
                    delete *it;

                P[i][j]->clear();
                delete P[i][j];
            }
            delete[] P[i];
        }
        delete[] P;
    }

    sizeP = 0;
}

Graph::Graph() {
    sizeG = 0;
    diameter = 0;
    T = NULL;
    _T = NULL;
    W = NULL;
    actived_node = NULL;

    R = NULL;
    C = NULL;
    E = NULL;
}

Graph::Graph(int G_size) {
    sizeG = G_size;
    diameter = 0;
    T = new list<int>;
    _T = new int[sizeG];
    W = new int[sizeG];
    actived_node = new int[sizeG];

    R = new int*[sizeG];
    C = new int*[sizeG];
    E = new int*[sizeG];
    for (int i = 0; i < sizeG; i++) {
        C[i] = new int[sizeG];
        E[i] = new int[sizeG];
        R[i] = new int[sizeG];
    }


    for (int i = 0; i < sizeG; i++) {
        _T[i] = 0;
        W[i] = 0;
        actived_node[i] = 0;

        for (int j = 0; j < sizeG; j++) {
            C[i][j] = 0;
            E[i][j] = 0;
            R[i][j] = 0;
        }
    }
}

Graph::Graph(Graph* G) {
    sizeG = G->sizeG;
    diameter = G->diameter;
    T = new list<int>;

    for (list<int>::iterator it = G->T->begin(); it != G->T->end(); ++it)
        T->push_front(*it);

    _T = new int[sizeG];
    W = new int[sizeG];
    actived_node = new int[sizeG];

    R = new int*[sizeG];
    C = new int*[sizeG];
    E = new int*[sizeG];
    for (int i = 0; i < sizeG; i++) {
        C[i] = new int[sizeG];
        E[i] = new int[sizeG];
        R[i] = new int[sizeG];
    }


    for (int i = 0; i < sizeG; i++) {
        _T[i] = G->_T[i];
        W[i] = G->W[i];
        actived_node[i] = G->actived_node[i];

        for (int j = 0; j < sizeG; j++) {
            C[i][j] = G->C[i][j];
            E[i][j] = G->E[i][j];
            R[i][j] = G->R[i][j];
        }
    }

}

void Graph::Add(Path* p) {
    list<int>::iterator _it, end;

    end = p->path->end();
    end--;
    for (list<int>::iterator it = p->path->begin(); it != end; ++it) {
        _it = it;
        _it++;
        actived_node[*it] = 1;
        SetMatrix(E, *it, *_it, 1);
    }
    actived_node[p->path->back()] = 1;
}

void Graph::Add(list<int>* p) {
    list<int>::iterator _it, end;

    end = p->end();
    end--;
    for (list<int>::iterator it = p->begin(); it != end; ++it) {
        _it = it;
        _it++;
        actived_node[*it] = 1;
        SetMatrix(E, *it, *_it, 1);
    }
    actived_node[p->back()] = 1;
}

void Graph::Add(list<list<int>*>* lista_p) {
    for (list<list<int>*>::iterator it = lista_p->begin(); it != lista_p->end(); ++it)
        Add(*it);
}

void Graph::Substract(Path* p) {

    list<int>::iterator _it, end;

    end = p->path->end();
    end--;
    for (list<int>::iterator it = p->path->begin(); it != end; ++it) {
        _it = it;
        _it++;
        actived_node[*it] = 0;
        SetMatrix(E, *it, *_it, 0);
    }
    actived_node[p->path->back()] = 0;
}

void Graph::Substract(list<int>* p) {

    list<int>::iterator _it, end;

    end = p->end();
    end--;
    for (list<int>::iterator it = p->begin(); it != end; ++it) {
        _it = it;
        _it++;
        actived_node[*it] = 0;
        SetMatrix(E, *it, *_it, 0);
    }
    actived_node[p->back()] = 0;
}

void Graph::SubstractWithoutExtremes(Path * p) {

    list<int>::iterator _it, end;
    int _e;
    //imprimirLista2(p->path, "Saco extremos al camino");
    int u = p->path->front();
    int v = p->path->back();

    end = p->path->end();
    end--;
    for (list<int>::iterator it = p->path->begin(); it != end; ++it) {
        _it = it;
        _it++;
        if (*it != u && *it != v) actived_node[*it] = 0;
        SetMatrix(E, *it, *_it, 0);
    }

    _e = p->path->back();
    if (_e != u && _e != v) actived_node[_e] = 0;
}

void Graph::SubstractWithoutExtremes(list<int> * p) {

    list<int>::iterator _it, end;
    int _e;
    //imprimirLista2(p->path, "Saco extremos al camino");
    int u = p->front();
    int v = p->back();

    end = p->end();
    end--;
    for (list<int>::iterator it = p->begin(); it != end; ++it) {
        _it = it;
        _it++;
        if (*it != u && *it != v) actived_node[*it] = 0;
        SetMatrix(E, *it, *_it, 0);
    }

    _e = p->back();
    if (_e != u && _e != v) actived_node[_e] = 0;
}

void Graph::Substract(list<Path*> * paths) {
    for (list<Path*>::iterator it = paths->begin(); it != paths->end(); ++it)
        Substract(*it);
}

void Graph::Substract(list<list<int>*> * paths) {
    for (list<list<int>*>::iterator it = paths->begin(); it != paths->end(); ++it)
        Substract(*it);
}

void Graph::SubstractWithoutExtremes(list<Path*> * paths) {
    for (list<Path*>::iterator it = paths->begin(); it != paths->end(); ++it)
        SubstractWithoutExtremes(*it);
}

void Graph::SubstractWithoutExtremes(list<list<int>*> * paths) {
    for (list<list<int>*>::iterator it = paths->begin(); it != paths->end(); ++it)
        SubstractWithoutExtremes(*it);
}

int Graph::GetNodeGrade(int node) {
    int grade = 0;

    if (actived_node[node]) {
        for (int i = 0; i < sizeG; i++)
            if (actived_node[i] && GetMatrix(E, node, i))
                grade++;
    }

    return grade;
}

bool Graph::IsTerminal(int node) {
    return (actived_node[node] && _T[node]);
};

list<int> * Graph::GetNeighbors(int node) {
    list<int> * neighbors = new list<int>;

    if (actived_node[node]) {
        for (int i = 0; i < sizeG; i++)
            if (actived_node[i] && GetMatrix(E, node, i)) neighbors->push_front(i);
    }

    return neighbors;
}

list<int> * Graph::GetNeighbors(int node, list<int> * candidates) {

    list<int> * neighbors = new list<int>;

    if (actived_node[node]) {
        for (list<int>::iterator it = candidates->begin(); it != candidates->end(); ++it)
            if (actived_node[*it] && GetMatrix(E, node, *it)) neighbors->push_front(*it);
    }

    return neighbors;
}

int Graph::Cost() {
    //cout << "////////////////////////////////////////////////////////////////DELETE BEFORE Cost()" << endl;
    int cost = 0;

    for (int i = 0; i < sizeG; i++) {
        if (actived_node[i]) {
            cost += W[i];
            for (int j = i; j < sizeG; j++)
                if (actived_node[j] && E[i][j]) cost += C[i][j];
        }
    }

    //cout << "///////////////////////////////////////////////////////////////DELETE AFTER Cost()" << endl;
    return cost;
}

int Graph::CostPath(Path * p) {

    int cost = 0;

    list<int>::iterator _it, end;
    end = p->path->end();
    end--;
    for (list<int>::iterator it = p->path->begin(); it != end; ++it) {
        _it = it;
        _it++;
        //cout << W[*it] << "   " << GetMatrix(C, *it, *_it) << "   " << *it+1 << "   " << *_it+1 <<endl;
        cost += W[*it] + GetMatrix(C, *it, *_it);
    }

    //cout << W[p->path->back()] << "   " << p->path->back()+1 <<endl;
    cost += W[p->path->back()]; // sumo el ultimo nodo que quedo sin sumar

    return cost;
}

int Graph::CostListInt(list<int> * l) {
    int cost = 0;
    //this->imprimirLista(l, "Lista Costo: ");
    list<int>::iterator _it, end;
    end = l->end();
    end--;
    for (list<int>::iterator it = l->begin(); it != end; ++it) {
        _it = it;
        _it++;
        //cout << W[*it] << "   " << GetMatrix(C, *it, *_it) << "   " << *it+1 << "   " << *_it+1 <<endl;
        //cost += W[*it] + GetMatrix(C, *it, *_it);
        cost += GetMatrix(C, *it, *_it);
    }

    //cout << W[p->path->back()] << "   " << p->path->back()+1 <<endl;
    //cost += W[l->back()]; // sumo el ultimo nodo que quedo sin sumar FIXME-- esto daba problemas 


    return cost;
}

Graph::Graph(const char* path) {
    sizeG = 0;
    diameter = 0;
    T = NULL;
    _T = NULL;
    W = NULL;
    actived_node = NULL;

    R = NULL;
    C = NULL;
    E = NULL;

    FileToGraph(path, this);
}

void Graph::Dump(char * file_path) {
    ofstream file(file_path);

    if (file.is_open()) {
        if ((sizeG > 0) && actived_node && E && _T) {

            file << "SECTION Nodes" << endl;
            for (int i = 0; i < sizeG; i++)
                if (actived_node[i]) {
                    if (_T[i])
                        file << "T " << i + 1 << " " << W[i] << endl;
                    else
                        file << "O " << i + 1 << " " << W[i] << endl;
                }

            file << "END" << endl;

            file << endl;

            file << "SECTION Edges" << endl;
            for (int i = 0; i < sizeG; i++)
                if (actived_node[i]) {
                    for (int j = i; j < sizeG; j++)
                        if (actived_node[j] && E[i][j])
                            file << "E " << i + 1 << " " << j + 1 << " " << C[i][j] << endl;
                }
            file << "END" << endl;

            file << endl;

            file << "SECTION Cost" << endl;
            file << "C " << Cost() << endl;
            file << "END" << endl;

        } else {
            file << "[ERROR][Graph::Dump]: Graph infeasible, some attributes are null." << endl;
        }


        file.close();
    } else cout << "[ERROR][Graph::Dump]: Unable to open file" << endl;
}

Graph::~Graph() {
    if (T) {
        T->clear();
        delete T;
    }

    if (_T) delete[] _T;

    if (W) delete[] W;
    if (actived_node) delete[] actived_node;

    if (C && R && E) {
        for (int i = 0; i < sizeG; i++) {
            if (C[i]) delete[] C[i];
            if (R[i]) delete[] R[i];
            if (E[i]) delete[] E[i];
        }

        delete[] R;
        delete[] C;
        delete[] E;
    }

    sizeG = 0;
    diameter = 0;
}

list<int>* Graph::getKeyNodes() {
    //int* keyNodes;
    list<int> * keyNodes = new list<int>;
    //recorremos todos los nodos
    for (int i = 0; i<this->sizeG; i++) {
        if (!this->IsTerminal(i) && this->GetNodeGrade(i) > 2) {
            keyNodes->push_front(i);
        }
    }
    return keyNodes;

}

list<list<int>*>* Graph::getKeyTree(int v) {
    list<list<int>*>* kTree = new list<list<int>*>;
    list<int>* adyacentes = this->GetNeighbors(v);
    int u;
    list<int>* kPath;
    for (list<int>::iterator it = adyacentes->begin(); it != adyacentes->end(); it++) {
        kPath = new list<int>; //creamos camino 
        kPath->push_back(v); // agregamos v al camino
        u = *it; //primer nodo adyacente
        int anterior = v; //recuerdo de donde vengo

        while (!this->IsTerminal(u) && this->GetNodeGrade(u) == 2) {
            kPath->push_back(u); //agregamos u al camino 
            list<int>* adyacentesAux = this->GetNeighbors(u);
            int aux = u;
            u = adyacentesAux->back(); //obtengo nodo adyacente
            if (u == anterior) { // si es igual a v, estoy yendo para "atras"
                u = adyacentesAux->front(); // entonces tomo otro nodo
            }
            anterior = aux;
        }
        //u ahora es raiz
        kPath->push_back(u); //agregamos u al camino 
        kTree->push_back(kPath);
    }
    return kTree;

}

list<int>* Graph::auxHojasKTree(list<list<int>*>* kTree) {
    list<int>* hojasKTree = new list<int>;
    list<int>* kPath;
    int hoja;
    for (list<list<int>*>::iterator it = kTree->begin(); it != kTree->end(); it++) {
        kPath = *it;
        hoja = kPath->back();
        hojasKTree->push_back(hoja);
    }
    return hojasKTree;
}

list<int>* Graph::auxNodosSteinerKTree(list<list<int>*>* kTree) {
    list<int>* nodosSteiner = new list<int>;
    list<int>::iterator itInsert = nodosSteiner->begin();
    list<int>* kPath;
    for (list<list<int>*>::iterator it = kTree->begin(); it != kTree->end(); it++) {
        kPath = new list<int>(*(*it));
        kPath->pop_back(); // saca la hoja
        kPath->pop_front(); // raiz
        nodosSteiner->insert(itInsert, kPath->begin(), kPath->end());
    }
    return nodosSteiner;
}

Graph* Graph::subGrafoInducidoMasAristas(list<int>* conjNodos, list<int>*Zv) {
    //Graph* Gtecho = new Graph();
    Graph* Gtecho = new Graph(this->sizeG + 1);
    //Gtecho->sizeG = this->sizeG + 1; // agregamos w, nodo ficticio al final
    Gtecho->diameter = this->diameter;
    //generamos las matrices del nuevo subgrafo 

    for (int i = 0; i < Gtecho->sizeG - 1; i++) {
        Gtecho->_T[i] = this->_T[i];
        //seteamos las aristas y sus costos inducidos por los costos
        for (list<int>::iterator it = conjNodos->begin(); it != conjNodos->end(); it++) {
            Gtecho->E[i][*it] = this->E[i][*it];
            Gtecho->C[i][*it] = this->C[i][*it];
            Gtecho->actived_node[*it] = 1;
        }
    }
    Gtecho->T = new list<int>(*(this->T)); //FIXME pierdo memoria

    //this->imprimirLista(Gtecho->T, "armamos bien los terminales?:::");

    int w = Gtecho->sizeG - 1;
    for (list<int>::iterator it = Zv->begin(); it != Zv->end(); it++) {
        Gtecho->E[w][*it] = 1;
        Gtecho->E[*it][w] = 1;
    }
    Gtecho->actived_node[w] = 1;


    return Gtecho;

}

bool interseccionKTreeConPath(list<list<int>*>* kTree, list<int>* p) {
    //iteramos primero sobre p
    for (list<int>::iterator it = p->begin(); it != p->end(); it++) {

        for (list<list<int>*>::iterator it2 = kTree->begin(); it2 != kTree->end(); it2++) {
            if (Contains(*it2, *it) == 1) {
                return true;
            }
        }
    }
    return false;
}


void DFS_vuelta(Graph* g, int x, int required, int d, list<int>* s, bool* visitados);

void DFS(Graph* g, int x, int required, int d) {
    list<int>* s = new list<int>;

    int n = g->sizeG;
    bool *visited = new bool[n + 1];
    int i;
    for (i = 0; i <= n; i++) {
        visited[i] = false;
    }
    s->push_front(x);
    visited[x] = true;
    if (x == required) {
        //chequear diametro
        DFS_vuelta(g, required, x, d, s, visited);
        return;
    }
    cout << "Depth first Search starting from vertex ";
    cout << x << " : " << endl;
    while (!s->empty()) {
        int k = s->front();
        s->pop_front();
        if (k == required) break;
        cout << k << " ";
        for (i = n; i >= 0; --i) {
            if (g->E[k, i] && !visited[i]) {
                s->push_front(i);
                visited[i] = true;
            }
        }
    }
    cout << endl;
    delete [] visited;
}

void DFS_vuelta(Graph* g, int x, int required, int d, list<int>* s, bool* visitados) {
    int n = g->sizeG;
    bool *visited = new bool[n + 1];
    int i;

    if (x == required) {
        //chequear diametro
        //DFS(g, required, x, s);
        return;
    }
    cout << "Depth first Search starting from vertex ";
    cout << x << " : " << endl;
    while (!s->empty()) {
        int k = s->front();
        s->pop_front();
        if (k == required) break;
        cout << k << " ";
        for (i = n; i >= 0; --i) {
            if (g->E[k, i] && !visited[i]) {
                s->push_front(i);
                visited[i] = true;
            }
        }
    }
    cout << endl;
    delete [] visited;
}

void dosCaminosNodosDisjuntosAcotados() {

}

bool Graph::esFactible() {
    //list<list<int>*>* L = new list<list<int>*>;
    list<list<int>*>* aux = new list<list<int>*>;
    //cout << "::Es factible" << endl;
    //this->imprimirLista(T, "Lista de terminales dentro de es factible");
    for (int i = 0; i<this->sizeG; i++) {
        if (this->_T[i] == 1) {
            //cout << i << " es un nodo terminal" << endl;
            for (int j = 0; j<this->sizeG; j++) {
                if ((i < j)&&(this->_T[j] == 1)) {
                    //      cout << j << " es un nodo terminal, entonces busco un camino entre" << i<<" y " << j << endl;
                    aux = this->caminoNodoDisjuntos(i, j);
                    //this->imprimirKtree(aux, "...Imprimiendo caminos de es factible.");
                    if (aux->size() < 2) {
                        //           cout << "\tes factible da falso" << endl;
                        return false;
                    }
                }
            }
        }
    }

    //cout << "\tes factible da true" << endl;
    return true;
    //this->imprimirLista(this->T,"\t nodos terminales");
    //armamos el conjunto de todos los caminos nodos disjuntos entre todo par de terminales

    //    for (list<int>::iterator it = this->T->begin(); it != this->T->end(); it++) {
    //        for (list<int>::iterator it2 = this->T->begin(); it2 != this->T->end(); it2++) {
    //            if (*it>*it2) {
    //                aux = this->caminoNodoDisjuntos(*it, *it2);
    //                this->imprimirKtree(aux, "...Imprimiendo caminos de es factible.");
    //                if (aux->size() < 2) {
    //                    return false;
    //                }
    //            }
    //        }
    //    }
}

void opciones_nodo_gv(bool esTerminal, char* &opciones) {
    if (esTerminal) {
        strcpy(opciones, "shape = doublecircle");
    } else {
        strcpy(opciones, "shape = circle");
    }
}

void Graph::graph_viz(const char* rutaSalida, const char* nombreGrafo) {
    char* opciones = new char[50];
    //char* ruta = "/home/emi/grafos/";
    char* rutaCompleta = new char[50];
    sprintf(rutaCompleta, "%s/graphviz/%s.gv", rutaSalida, nombreGrafo);

    ofstream file(rutaCompleta);
    if (file.is_open()) {
        if ((sizeG > 0) && actived_node && E && _T) {
            file << "graph g{" << endl;
            for (int i = 0; i < sizeG; i++)
                if (actived_node[i]) {
                    opciones_nodo_gv(this->_T[i], opciones);
                    file << i << " [" << opciones << "];" << endl;
                }
            for (int i = 0; i < sizeG; i++)
                if (actived_node[i]) {
                    for (int j = i; j < sizeG; j++)
                        if (actived_node[j] && E[i][j]) {
                            //file << "E " << i + 1 << " " << j + 1 << " " << C[i][j] << endl;
                            file << "\t" << i << "--" << j << " [ label=" << this->C[i][j] << "];" << endl;
                        }
                }
            file << endl;

        } else {
            cout << "[ERROR][Graph::Dump]: Graph infeasible, some attributes are null." << endl;
        }
        file << "}" << endl;
        file.close();
    } else cout << "[ERROR][Graph::Dump]: Unable to open file" << endl;
}

void Graph::imprimirLista(list<int>* L, const char* mensaje) {
    cout << mensaje << ":: ";
    for (list<int>::iterator it = L->begin(); it != L->end(); it++) {
        cout << *it << " ";
    }
    cout << " :: EOL" << endl;
}

void Graph::imprimirKtree(list<list<int>*>* kTree, const char* mensaje) {
    int cont = 1;
    cout << mensaje << endl;
    for (list<list<int>*>::iterator it = kTree->begin(); it != kTree->end(); it++) {
        cout << "\t" << cont++;
        imprimirLista(*it, "-esima rama de kTree");
    }
}

void Graph::sub_graph_viz(Graph* H, const char* rutaSalida, const char* nombreGrafo) {
    char* opciones = new char[50];
    //char* ruta = "/home/emi/grafos/";
    char* rutaCompleta = new char[100];
    sprintf(rutaCompleta, "%s/graphviz/%s-solucion.gv", rutaSalida, nombreGrafo);

    ofstream file(rutaCompleta);
    if (file.is_open()) {
        if ((sizeG > 0) && actived_node && E && _T) {
            file << "graph g{" << endl;
            for (int i = 0; i < sizeG; i++)
                if (actived_node[i]) {
                    opciones_nodo_gv(this->_T[i], opciones);
                    file << i << " [" << opciones << "];" << endl;
                }
            for (int i = 0; i < sizeG; i++) {
                if (actived_node[i]) {
                    for (int j = i; j < sizeG; j++)
                        if (actived_node[j] && E[i][j]) {
                            //file << "E " << i + 1 << " " << j + 1 << " " << C[i][j] << endl;
                            file << "\t" << i << "--" << j << " [ label=" << this->C[i][j] << "];" << endl;
                        }
                }
            }
            for (int i = 0; i < H->sizeG; i++) {
                if (H->actived_node[i]) {
                    for (int j = i; j < H->sizeG; j++)
                        if (H->actived_node[j] && H->E[i][j]) {
                            //file << "E " << i + 1 << " " << j + 1 << " " << C[i][j] << endl;
                            file << "\t" << i << "--" << j << " [ penwidth = 3, color=\"#ff0000\"];" << endl;
                        }
                }
            }

            file << endl;

        } else {
            cout << "[ERROR][Graph::Dump]: Graph infeasible, some attributes are null." << endl;
        }
        file << "}" << endl;
        file.close();
    } else cout << "[ERROR][Graph::Dump]: Unable to open file" << endl;
};

void colorArista(int c, char* &opciones) {
    switch (c % 7) {
        case 0: strcpy(opciones, "red");
            break;
        case 1: strcpy(opciones, "green");
            break;
        case 2: strcpy(opciones, "blue");
            break;
        case 3: strcpy(opciones, "yellow");
            break;
        case 4: strcpy(opciones, "darkorchid");
            break;
        case 5: strcpy(opciones, "fuchsia");
            break;
        case 6: strcpy(opciones, "yellow");
            break;
    }
}

void Graph::subLista_graph_viz(list<Path*>* LP, int orig, int dest, const char* nombreGrafo) {
    char* opciones = new char[50];
    char* rutaCompleta = new char[50];
    sprintf(rutaCompleta, "%s%s-%d-%d.gv", "/home/emi/grafos/", nombreGrafo, orig, dest);

    ofstream file(rutaCompleta);
    if (file.is_open()) {
        if ((sizeG > 0) && actived_node && E && _T) {
            file << "graph g{" << endl;
            for (int i = 0; i < sizeG; i++)
                if (actived_node[i]) {
                    opciones_nodo_gv(this->_T[i], opciones);
                    file << i << " [" << opciones << "];" << endl;
                }
            for (int i = 0; i < sizeG; i++) {
                if (actived_node[i]) {
                    for (int j = i; j < sizeG; j++)
                        if (actived_node[j] && E[i][j]) {
                            //file << "E " << i + 1 << " " << j + 1 << " " << C[i][j] << endl;
                            file << "\t" << i << "--" << j << " [ label=" << this->C[i][j] << "];" << endl;
                        }
                }
            }
            int cont=0;
            for (list<Path*>::iterator it = LP->begin(); it != LP->end(); it++) {
                list<int>* p = (*it)->path;
                list<int>::iterator it2 = p->begin();
                int izquierda = *it2;
                int derecha;
                it2++;
                
                for (it2; it2 != p->end(); it2++) {
                    derecha = *it2;
                    colorArista(cont, opciones);
                    file << "\t" << izquierda << "--" << derecha << " [ color=" << opciones << " ];" << endl;
                    izquierda = derecha;
                }
                cont++;
            }


            file << endl;

        } else {
            cout << "[ERROR][Graph::Dump]: Graph infeasible, some attributes are null." << endl;
        }
        file << "}" << endl;
        file.close();
    } else cout << "[ERROR][Graph::Dump]: Unable to open file" << endl;
};

void Graph::agregarArista(int origen, int destino, int costo) {
    
//    this->C[origen][destino] = costo;
//    this->C[destino][origen] = costo;
//    
//    this->E[origen][destino] = 1;
//    this->E[destino][origen] = 1;
    
    SetMatrix(this->C, origen, destino, costo);
    SetMatrix(this->E, origen, destino, 1);
    if(this->_T[origen] && this->_T[destino]){
        SetMatrix(this->R, origen, destino, 2);
    }
    
    
}

